package 回溯算法;


import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class 分割回文串 {
    class Solution{
        ArrayList<List<String>> list = new ArrayList<>();
        Deque<String> deque = new LinkedList<>();

        public List<List<String>> partition(String s ){
            backTracking(s,0);
            return list;

        }

        public void backTracking(String s, int startIndex) {
            if (startIndex >= s.length()){
                list.add(new ArrayList<>(deque));
                return;
            }
            for (int i = startIndex; i < s.length(); i++) {
                if (isPalindrome(s,startIndex,i)){
                    //substring的参数从beginIndex开始取，到endIndex结束，**从0开始数，其中不包括endIndex位置的字符**
                    String str = s.substring(startIndex,i+1);
                    deque.addLast(str);
                }else {
                    continue;
                }
                //向下遍历了
                backTracking(s,i+1);
                //回溯
                deque.removeLast();
            }

        }

        private boolean isPalindrome(String s, int startIndex, int end) {
            for (int i=startIndex,j=end;i>0&&j<s.length();i++,j--){
                if (s.charAt(i) != s.charAt(j)){
                    return false;
                }
            }

            return true;
        }


    }
}
